The security of a technical system or corresponding technical process is per se of technical nature involving a technical understanding of underlying system vulnerabilities and security threats. Examples of technical systems that may be of interest from a security aspect include industrial processing systems such as more or less automated manufacturing processes, information/communication systems and transportation systems. Such systems contain tangible or non-tangible assets which motivates malicious parties into attempting to attack the systems in order to take control over these assets. However, in some cases the attacker(s) may be more interested in the reputation obtained from (successfully) attacking the system than the asset itself. This is for instance common among “computer hackers”.
It may be useful to begin by describing some conventional concepts in the field of general security analysis. Although some of the examples presented below are rather simple for improved understanding of the underlying concepts, it should be understood that in practice the systems under consideration are always technical systems. Often, the technical systems are rather complex systems with technical relations and dependencies on multiples levels.
A Brief Introduction to the Attack Tree Concept
The Attack Tree (AT) concept was introduced by Bruce Schneier in [11]. The following introduction is based on this reference, but is slightly modified.
What is an Attack Tree?
An attack tree is a way to represent knowledge of the vulnerabilities of a technical system. That knowledge has to be acquired in some way, and for that, ATs are only marginally useful. This is an important point to make, that ATs do not add knowledge about what security threats there are, but instead they provide a way to represent the knowledge and facilitating the process of determining the relative importance of the threats.
Attack Tree Construction
An attack tree is ideally constructed with a top-down, divide-and-conquer approach. The concept can easily be understood by a simple example where the attacker is trying to open a safe (most likely motivated by the prospect of gaining access to the safe's content). Thus, the technical system in question is a safe, and the asset that is being threatened is the contents of the same. The first step is to define the goal of the attack that one wants to analyze. In the example the goal of the attack is to open a safe (“open safe”). This is placed as the root node in the attack tree as can be seen in FIG. 1A.
The next step is to figure out how this can be achieved and there could be more than one way. After a thorough analysis of the technical environment and every other relevant aspect, it may be decided that there are only two possible ways of doing this: by cutting the safe open or by opening the lock. These two actions are added as predecessors to the root, as depicted in FIG. 1B.
Now comes the conquer-step: each of the two added nodes is analyzed to establish all possible ways of achieving them. In this case, it is decided that cutting up the safe is simple enough so that it is does not need any further refinement. Here, simple is not the same as easy. Instead, an action is considered simple when it is clear how it is performed, no matter the degree of difficulty. An action that has been refined to a point where no further refinement is needed is called an atomic attack. The other way of opening the safe, by opening the lock, is on the other hand not refined to satisfactory degree. It is therefore further analyzed how this action can be performed, and in this case, it is decided that there are three different ways of doing it: by using a locksmith, by stealing the combination or by eavesdropping to obtain the combination. Thus these three ways are added as predecessors to the “open lock” node, as can be seen in FIG. 1C. Although this example is quite simplified, it should be clear that there is a direct relation between an attack tree and physical/technical influence on the system.
The three nodes are analyzed exactly as above. In the example, it is decided that eavesdropping the combination should be considered to be an atomic attack, whereas using the locksmith can be achieved by convincing him to do it or bribing him to do it.
The third way, eavesdropping the combination, can be achieved only by getting the combination stated in some way while at the same time listening to the conversation. This makes the eavesdropping a so called and-node, as all its predecessors has to be accomplished in order to accomplish the sub-attack that it represents. This contrasts all other nodes discussed this far, which have been or-nodes, i.e., they are nodes that can be accomplished by achieving only one of their direct predecessors. Graphically, an and-node is represented as a box instead of a round shape as is the case for or-nodes, and the arrows going into it have small circles as arrowheads instead of ordinary arrowheads, as in FIG. 2.
At this point it may be decided that there is no more need for refining any attack, i.e., all leaves are considered as being atomic attacks. The attack tree is therefore considered complete, and all our knowledge about the threat is now represented in the tree. The decision about when a node is considered to be of sufficient simplicity to qualify as an atomic attack, is left entirely up to the constructor, and has to be made individually for each tree constructed.
In the example above we only considered a single threat/attack to the technical system. In general there could be a plurality of threats that needs to be understood and this general case will be discussed later.
Attack Tree Analysis
Now that the threat is modeled as an attack tree from a qualitative point of view, it can be used to evaluate or “measure” the security of the technical system at hand in a more quantitative way. This is done by first “rating” the atomic attacks according to some attribute that is sought to evaluate, and then deriving the attribute value for the whole system. This is, as with the construction of an attack tree, best explained by an example.
As an example, suppose that there is interest in whether or not the threat of opening the safe is at all possible to realize, i.e. a “Boolean” attribute.
The first step is to rate the atomic attacks in the tree as whether or not they are possible (under a given set of conditions/assumptions). The result can be seen in FIG. 3, where I stands for Impossible and P stands for Possible. Now, the following, quite natural, two rules are used:
1. An or-node is defined to be possible if, and only if, at least one of its predecessors is possible.
2. An and-node is defined to be possible if, and only if, all its predecessors are possible.
Using these two rules and the assignment of (im)possibilities to each atomic attack, the possibility or impossibility can be derived for each of the non-atomic attacks in the tree in a very simple “bottom-up” way. The result of doing this with the given example is shown in FIG. 4.
As can be seen from FIG. 4, the threat is possible to realize. It is also clear how this threat can be realized: by opening the lock by using a locksmith that is bribed. In the example, this is the only way. In more general cases, the possible realization(s) of the threat can be found in terms of path(s) from the root, where all labels in the path(s) have P-labels. The possibility/impossibility is not the only attribute that is discussed in [11]. Other attributes proposed is the difficulty (e.g. time/skills needed) of the easiest attack, the need for the attacker to use special equipment for all attacks (e.g. all attacks require use of power-drill), the cost (in terms of money/resources) of the cheapest attack, etc. For each of these, the way to derive the value of an or-node and an and-node must be decided in a way that seems reasonable. As an example, the two rules for computing the cost of the cheapest attack, corresponding to the rules above when the possibility was discussed, could be the following, quite natural definitions:
1. The cost of an or-node equals the minimum of the cost of its predecessors
2. The cost of an and-node equals the sum of the cost of its predecessors
Using the previous attack tree and instead computing the minimum cost attribute, the resulting tree will look like FIG. 5, given the therein depicted set of costs of the atomic attacks.
Note that the atomic attacks are rated with different sets of initial conditions in these two examples. As an example, the cost of convincing the locksmith is irrelevant when it is impossible. If the initial conditions are indeed the same, then the tree needs pruning of the impossible nodes before a meaningful analysis of other attributes can be performed.
After having derived information about the cost, difficulty and need for special equipment, the overall security of the system can be assessed by considering who the adversary is. If it is some entity with potentially infinite monetary resources but with little knowledge, then it is of course important that the attack is technically hard to realize, but whether it is expensive or not is of little importance. On the other hand, if the adversary is a brilliant computer hacker, then the high cost and the need for some hard-to-get special equipment is important, but the difficulty of breaking in might be of less importance as it is assumed that the hacker can do almost anything possible with a computer. It is when the result of the analysis is combined with the information about the attacker that proper decisions about countermeasures can be made, and this point is heavily emphasized in [11].
It was mentioned at the start of this section that ATs could be of some help in analyzing the threats, and not only in representing the result of the analysis. The idea is that the analyzer of the system gets a way of systematically covering all aspects in depth, and this structured approach could reduce the risk of overseeing a possible threat. Of course, the analysis is always ultimately dependent on the analyzer.
Automation
The above examples can be considered “toy” examples only serving the purpose of explaining how attack trees can be used. In a large, complex technical system the associated attack tree can be quite large, However, as one of ordinary skill in the art can realize, the above discussed methods of traversing the attack tree from leaves to root can easily be automated by an apparatus, thus propagating values upward according to the two rules for “and/or” vertices.
Numerous papers have been published in this field, as well as in other related areas.
In [8], a more formal treatment of attack trees can be found. The authors provide a mathematically rigorous framework for attack trees and the algorithms for propagation and projections described in [11]. However, this theory does not allow for all possible types of (non-tree) graphs, and therefore cannot be used as it is. The very nature of the theory makes it impossible to extend in a straight-forward way, and thus it becomes less interesting.
Attack Graphs
The subject of attack graphs, studied mainly at Camiege Mellon University, bears similarity in the name to attack trees. However, this is where the similarity ends, as the concept differs entirely from attack trees. The aim of attack graphs is to derive, from a model of the system, all the possible attacks on the system and ultimately devise a set of actions to prevent these possibilities. The main method used is to specify the set of safe states S in the network model that satisfies a desired property (capturing that the system is free of security breeches), and then use standard model checking techniques to generate the executions, if any, in the model which reach some state not in S. Since reaching such a state would mean a security breech, the system is secure if no such state can be reached. Put differently, determining if an attack can be mounted is the same as solving a graph reachability problem. Attack graphs have advantages, but also disadvantages compared to attack trees. First, attack graphs are mainly concerned with deducing whether there exists an attack. Attack graphs can be used to find an “optimal” countermeasure that will thwart the attack. Unfortunately, finding this optimal countermeasure resorts to solving NP-complete graph problems, which may be practically infeasible and one would need to settle for an approximately optimal countermeasure. Moreover, “optimal” is only quantified by the number of changes needed in the abstract graph representation of the system. In practice, one may be more interested in the countermeasures that are most practically feasible which could very well be some completely different countermeasures. Other quantitative aspects are not at all taken into account. For more background on attack graphs, see [12].
Augmented Attack Trees
Various extensions have been made to the attack tree concept. In [7, 4], Tidwell et al extends the concept of attack trees with parameters, variables, sub goals and pre- and post conditions. They also introduce the concept of an Elevated Node Topology (ENT), which is a way to hierarchically cluster the nodes in an attack tree. This extension is then used as a part of a system for attack detection, in particular of attacks that consist of several, seemingly unrelated attacks. In [3] the hierarchical clustering is redefined as a Stratified Node topology (SNT), which is essentially the same as an ENT. The additional concept introduced in the SNT is that of implicit and explicit links in the attack tree. The difference between them is that an implicit link is used to describe an event automatically induced by some other event, whereas an explicit link describes the enabling of another attack, which is then not necessarily carried out. In [5], they thoroughly explain how to automatically generate attack trees via the notion of attack tree chaining from descriptions of the system. They also provide a very crude sketch of how to use the generated attack tree to analyze the probability of attacks on the system.
Another way of modeling threats against a system that was inspired by attack trees is the use of Petri Nets instead of just ordinary graphs. A Petri Net is a graph with some extra features: informally, it is a graph accompanied with a function describing the initial state of the Petri Net, and a relation with some additional restrictions describing the possible transitions of the system. The obvious way to visualize this is as a graph with tokens on its vertices, and some rules describing how the tokens move, allowing the number of tokens to vary from the start to the completion of a transition. For a more in-depth introduction of Petri Nets see [6, 15].
The above described research is, albeit intrinsically interesting, not of great use from a practical point of view when it comes to improving the system security. The main reason for it not being relevant is that there is a lot of focus on how to predict attacks from a description of a system, rather than analyzing an existing attack tree. Some of the ideas from Tidwell et al in [4, 5] are interesting and can serve as inspiration for extensions, in particular their discussion on parameters.
The use of Attack Nets as in [9] does indeed provide a more expressive model. In particular, the ability to have more complicated rules than just AND/OR nodes is interesting. However, if the model becomes more complicated the intuitiveness inherent in the simple AND/OR tree structure is lost. The tradeoff here seems too big for the particular application at hand.
Existing Tools
There are already some tools for the analysis of attack trees. Most notably there is the commercial tool called securITree from Amenaza Tech Ltd. The focus of the tool seems to be mainly the usability for people that are not very computer literate. For more information, see [1].
There is also a tool developed by Alexander Opel [10]. This tool contains some basic functionality for constructing attack trees as well as some types of analysis, but does not allow for more general cases. There are also some interesting points made in the report that are relevant in general to the design and implementation.
However, despite a plethora of work in this technical field, there is still a general demand for an efficient apparatus and/or tool for analyzing attacks to more general technical systems (in particular cases that cannot be modeled by trees or very simple graphs) and enabling proper reconfiguration of the technical system under consideration to improve system security.